package com.leetcode.study;

/**
 *  0-1 背包问题。
 *  在该问题中，给定一组物品，每个物品都有对应的价值和重量，同时有一个限定的背包容量。
 *  问题的目标是选择一些物品放入背包，使得放入背包的物品总价值最大，但是放入的物品总重量不超过背包的容量。
 *  动态规划：
 *  如果一个包放一个物品，递推为n个包放n个物品价值最大
 */
public class Knapsack01 {

    public static void main(String[] args) {

        int[] values = {6, 10, 12};
        int[] weights = {1, 2, 3};
        int W = 5;

        System.out.println(knapsack(W,weights,values));
        System.out.println(get(values, weights, W));
    }

    /**
     * copy from Internet
     * @param W
     * @param weights
     * @param values
     * @return
     */
    public static int knapsack(int W, int[] weights, int[] values) {
        int n = values.length;
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                if (weights[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
                }
            }
        }

        return dp[n][W];
    }

    /**
     * 1、定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时能够获得的最大价值。
     * 然后我们可以用状态转移方程来更新 dp 数组，最终得到 dp[n][W]，其中 n 是物品的个数，W 是背包的容量，即为所求的最大价值。
     *
     * 2、状态转移方程
     * a、dp[0][j] = 0
     *
     * b、dp[i][0] = 0
     *
     * c、dp[i][j] = max(放，不放) 最大值
     * 如果不放（j < weight 背包容量不足），就是上一次所求的最大价值，即：dp[i-1][j]
     * 如果放 j >= weight，放完之后，还剩下的重量上一次所获得的最大价值(dp[i-1][j - w]) +本次价值(values[i]) 和不放时(dp[i-1][j])，取最大值
     * dp[i][j] = Math.max(dp[i - 1][j], v[i] + dp[i-1][j - w]);
     *
     * @param values 价值
     * @param weights 重量
     * @param limit 背包容量
     * @return
     */
    private static int get(int[] values, int[] weights, int limit) {
        // 定义 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时能够获得的最大价值
        int[][] dp = new int[weights.length + 1][limit + 1];


        for (int i = 1; i <= weights.length; i++) {
            int w = weights[i -1 ];

            for (int j = 1; j <= limit; j++) {

                // 如果不放（j < weight 背包容量不足）
                // 就是上一次dp[i][j]即：dp[i-1][j]
                if (j < w) {
                    dp[i][j] = dp[i - 1][j];
                }
                // 如果放 j >= weight，放完之后，还剩下的重量上一次所获得的最大价值+本次价值
                // 和不放时，取最大值
                else {
                    int v = values[i-1] + dp[i-1][j - w];
                    dp[i][j] = Math.max(dp[i - 1][j], v);
                }
            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }

}
